#include<iostream>

// 采用设置虚拟头节点方法实现这六个接口
class MyLinkedList {
public:
    // 单链表
    struct ListNode
    {
        int val;
        ListNode *next;
        ListNode():val(0), next(nullptr){}
        ListNode(int x):val(x), next(nullptr){}
        ListNode(int x, ListNode *next):val(x), next(next){}
    };

    //初始化链表
    MyLinkedList() {
        dummy_head_ = new ListNode(0); //虚拟头节点，非真正头节点
        size_ = 0;
    }
    
    int get(int index) {
        if (index > size_-1 || index < 0)
        {
            return -1;
        }

        ListNode *current_node = dummy_head_->next;
        while (index--) //若写为--index，就会陷入死循环
        {
            current_node = current_node->next;
        }
        return (current_node == nullptr ? -1 : current_node->val);
    }
    
    void addAtHead(int val) {
        ListNode *new_node = new ListNode(val);
        new_node->next = dummy_head_->next;
        dummy_head_->next = new_node;
        size_++;
    }
    
    void addAtTail(int val) {
        ListNode *current_node = dummy_head_;
        while (current_node->next != nullptr)
        {
            current_node = current_node->next;
        }
        ListNode *new_node = new ListNode(val);
        current_node->next = new_node;
        size_++;
    }
    
    void addAtIndex(int index, int val) {
        if (index > size_)
        {
            return;
        }
        
        ListNode *new_node = new ListNode(val);
        ListNode *current_node = dummy_head_;
        while (index--)
        {
            current_node = current_node->next;
        }
        new_node->next = current_node->next;
        current_node->next = new_node;
        size_++;
    }
    
    void deleteAtIndex(int index) {
        if (index >= size_ || index < 0)
        {
            return;
        }
        
        ListNode *current_node = dummy_head_;
        while (index--)
        {
            current_node = current_node->next;
        }
        
        ListNode *tmp = current_node->next;
        current_node->next = current_node->next->next;
        delete tmp;
        size_--;
    }

    void printListNode()
    {
        ListNode *current_node = dummy_head_;
        while (current_node->next != nullptr)
        {
            std::cout << current_node->next->val << ", ";
            current_node = current_node->next;
        }
        std::cout << std::endl;
    }
private:
    ListNode *dummy_head_;
    int size_;
};

int main()
{
    MyLinkedList *myLinkedList = new MyLinkedList();
    
    // case1: 
    myLinkedList->addAtHead(7);
    std::cout << "1: "<< myLinkedList->get(0) <<std::endl;
    myLinkedList->addAtHead(2);
    std::cout << "2: "<< myLinkedList->get(0) <<", "<< myLinkedList->get(1) <<std::endl;
    myLinkedList->addAtHead(1);
    std::cout << "3: "<< myLinkedList->get(0) <<", "<< myLinkedList->get(1)<<", "<< myLinkedList->get(2) <<std::endl;
    myLinkedList->addAtIndex(3, 0);    
    std::cout << "4: "<< myLinkedList->get(0) <<", "<< myLinkedList->get(1)<<", "<< myLinkedList->get(2)<<", "<< myLinkedList->get(3) <<std::endl;
    myLinkedList->deleteAtIndex(2);
    std::cout << "5: "<< myLinkedList->get(0) <<", "<< myLinkedList->get(1)<<", "<< myLinkedList->get(2) <<std::endl;
    myLinkedList->addAtHead(6);
    std::cout << "6: "<< myLinkedList->get(0) <<", "<< myLinkedList->get(1)<<", "<< myLinkedList->get(2)<<", "<< myLinkedList->get(3) <<std::endl;
    myLinkedList->addAtTail(4);
    std::cout << "7: "<< myLinkedList->get(0) <<", "<< myLinkedList->get(1)<<", "<< myLinkedList->get(2)<<", "<< myLinkedList->get(3)<<", "<< myLinkedList->get(4) <<std::endl;
    myLinkedList->addAtHead(4);
    std::cout << "8: "<< myLinkedList->get(0) <<", "<< myLinkedList->get(1)<<", "<< myLinkedList->get(2)<<", "<< myLinkedList->get(3)<<", "<< myLinkedList->get(4)<<", "<< myLinkedList->get(5) <<std::endl;
    myLinkedList->addAtIndex(5, 0);
    std::cout << "9: "<< myLinkedList->get(0) <<", "<< myLinkedList->get(1)<<", "<< myLinkedList->get(2)<<", "<< myLinkedList->get(3)
    <<", "<< myLinkedList->get(4)<<", "<< myLinkedList->get(5) <<", "<< myLinkedList->get(6)<<std::endl;
    myLinkedList->addAtHead(6);
    std::cout << "10: "<< myLinkedList->get(0) <<", "<< myLinkedList->get(1)<<", "<< myLinkedList->get(2)<<", "<< myLinkedList->get(3)
    <<", "<< myLinkedList->get(4)<<", "<< myLinkedList->get(5) <<", "<< myLinkedList->get(6) <<", "<< myLinkedList->get(7)<<std::endl;
    
    /*
    // case2:   
    myLinkedList->addAtHead(1);
    std::cout << "1: "<< myLinkedList->get(0) <<std::endl;
    myLinkedList->addAtTail(3);
    std::cout << "2: "<< myLinkedList->get(0) <<", "<< myLinkedList->get(1) <<std::endl;
    myLinkedList->addAtIndex(1,2);
    std::cout << "3: "<< myLinkedList->get(0) <<", "<< myLinkedList->get(1)<<", "<< myLinkedList->get(2) <<std::endl;
    myLinkedList->deleteAtIndex(0);
    std::cout << "4: "<< myLinkedList->get(0) <<", "<< myLinkedList->get(1) <<std::endl;
    */
    return 0;
}